//
//  30.连续子数组最大和.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/21.
//

import Foundation
/*
 题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
 思路：典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可。
 */
func offer_30() {
    print(Solution().findGreatestSumOfSubArray([1,-2,3,10,-4,7,2,-5]))
}

fileprivate class Solution {
    func findGreatestSumOfSubArray(_ array: [Int]) -> Int {
        guard !array.isEmpty else { return Int.min }
        var array = array
        var res = array.first!
        for i in 1..<array.count {
            array[i] += array[i-1] > 0 ? array[i-1] : 0
            res = max(res, array[i])
        }
        return res
    }
}
